package com.wang.transfer.util.algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 2-9的任意数字组合
 * 回溯算法
 */
public class LetterCombinations {

    public static void main(String[] args) {
        String digits = "23";
        List<String> list = new LetterCombinations().letterCombinations(digits);
        System.out.println(list);
    }

    public static final Map<Character, char[]> map = new HashMap<>();

    public List<String> letterCombinations(String digits) {
        map.put('2', new char[]{'a', 'b', 'c'});
        map.put('3', new char[]{'d', 'e', 'f'});
        map.put('4', new char[]{'g', 'h', 'i'});
        map.put('5', new char[]{'j', 'k', 'l'});
        map.put('6', new char[]{'m', 'n', 'o'});
        map.put('7', new char[]{'p', 'q', 'r', 's'});
        map.put('8', new char[]{'t', 'u', 'v'});
        map.put('9', new char[]{'w', 'x', 'y', 'z'});
        List<StringBuilder> stringBuilders = letter(new ArrayList<>(), digits);
        List<String> list = new ArrayList<>();
        for (StringBuilder stringBuilder : stringBuilders) {
            list.add(stringBuilder.toString());
        }
        return list;
    }

    public List<StringBuilder> letter(List<StringBuilder> list, String digit) {
        if (digit.length() < 1) {
            return list;
        }
        char[] chars = map.get(digit.charAt(0));
        List<StringBuilder> stringBuilders = new ArrayList<>();
        for (int i = 0; i < (list.size() > 0 ? list.size() : chars.length); i++) {
            if (list.size() < 1) {
                stringBuilders.add(new StringBuilder().append(chars[i]));
            } else {
                int j = 0;
                do {
                    String str = list.get(i % list.size()).toString();
                    stringBuilders.add(new StringBuilder(str + chars[j]));
                } while (++j < chars.length);
            }
        }
        return letter(stringBuilders, digit.substring(1));
    }
}
